package p0;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_46 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        boolean[] flag = new boolean[nums.length];
        dfs(list, new ArrayList<Integer>(), flag, nums);
        return list;
    }

    private void dfs(List<List<Integer>> list, List<Integer> temp, boolean[] flag, int[] nums) {
        if (temp.size() == flag.length) {
            list.add(new ArrayList<Integer>(temp));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!flag[i]) {
                    temp.add(nums[i]);
                    flag[i] = true;
                    dfs(list, temp, flag, nums);
                    flag[i] = false;
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Leetcode_46 l = new Leetcode_46();
        System.out.println(l.permute(new int[]{1, 2, 3}));
    }
}
